// 前缀树节点定义
class TrieNode
{
public:
    bool isWord;
    vector<TrieNode*> child;

    TrieNode()
        : isWord(false)
        , child(26, nullptr)
    {}

    ~TrieNode()
    {
        for(auto c : child)
            delete c;
    }
};

class WordDictionary {
private:
    TrieNode *root;
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode *cur = root;
        for(auto &ch : word)
        {
            int i = ch - 'a';
            if(cur->child[i] == nullptr)
                cur->child[i] = new TrieNode(); 
            cur = cur->child[i];
        }
        cur->isWord = true;
    }
    
    bool match(string &word, TrieNode *cur, int index)
    {
        if(cur == nullptr)
            return false;
        if(word.size() == index)
            return cur->isWord;

        char ch = word[index];
        if(ch != '.')
        {
            return match(word, cur->child[ch - 'a'], index + 1);
        }
        else
        {
            for(auto &pchild : cur->child)
                if(match(word, pchild, index + 1))
                    return true;
        }
        
        return false;
    }

    bool search(string word) {
        return match(word, root, 0);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */